package xyz.sekai52799.answer.a2201_a2400;

import xyz.sekai52799.utils.TreeNode;

import java.util.*;

public class Question2385 {
//    给你一棵二叉树的根节点 root ，二叉树中节点的值 互不相同 。另给你一个整数 start 。在第 0 分钟，感染 将会从值为 start 的节点开始爆发。
//
//    每分钟，如果节点满足以下全部条件，就会被感染：
//
//    节点此前还没有感染。
//    节点与一个已感染节点相邻。
//    返回感染整棵树需要的分钟数。

    private int ans = 0;
    //
    public int amountOfTime(TreeNode root, int start) {
        // 转成无向图
        Map<Integer, List<Integer>> graph = new HashMap<>();
        dfs(graph, root, 0);
        Set<Integer> visited = new HashSet<>();
        dfs2(graph, start, visited, 0);
        return ans;
    }

    private void dfs(Map<Integer, List<Integer>> graph, TreeNode node, int fa){
        graph.putIfAbsent(node.val, new ArrayList<Integer>());
        if (fa != 0){
            graph.get(node.val).add(fa);
        }
        if (node.left != null){
            graph.get(node.val).add(node.left.val);
            dfs(graph, node.left, node.val);
        }
        if (node.right != null){
            graph.get(node.val).add(node.right.val);
            dfs(graph, node.right, node.val);
        }
    }

    private void dfs2(Map<Integer, List<Integer>> graph, int start, Set<Integer> visited, int depth){
        visited.add(start);
        ans = Math.max(ans, depth);
        if (graph.get(start) == null){
            return;
        }
        for (int n : graph.get(start)){
            if (visited.contains(n)){
                continue;
            }
            visited.add(n);
            dfs2(graph, n, visited, depth+1);
        }
    }
}
